package com.huangyi;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 二叉树节点定义
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 二叉树的所有路径
    static class Solution {
        private List<String> ans = new ArrayList<>();

        public List<String> binaryTreePaths(TreeNode root) {
            // 1) 边界处理
            if (root == null) return ans;
            
            // 2) 深度优先搜索收集所有路径
            dfs(root, new StringBuilder());
            return ans;
        }

        private void dfs(TreeNode node, StringBuilder path) {
            if (node == null) return;

            // 基于父层前缀复制一份本层专用缓冲
            StringBuilder cur = new StringBuilder(path);
            cur.append(node.val);

            // 3) 叶子节点：收集路径
            if (node.left == null && node.right == null) {
                ans.add(cur.toString());
                return; // 无需回溯
            }

            // 4) 继续遍历左右子树
            cur.append("->");
            dfs(node.left, cur);
            dfs(node.right, cur);
        }
    }

    // 全排列
    static class Solution2 {
        List<List<Integer>> result;
        List<Integer> path;
        boolean[] vis;

        public List<List<Integer>> permute(int[] nums) {
            // 1) 初始化
            int n = nums.length;
            result = new ArrayList<>();
            path = new ArrayList<>(n);
            vis = new boolean[n];
            
            // 2) 回溯搜索所有排列
            dfs(nums);
            return result;
        }

        private void dfs(int[] nums) {
            // 3) 命中叶子：收集一条排列
            if (path.size() == nums.length) {
                result.add(new ArrayList<>(path)); // 一定要拷贝
                return;
            }
            
            // 4) 遍历所有未使用的数字
            for (int i = 0; i < nums.length; i++) {
                if (vis[i]) continue;              // 已用跳过
                path.add(nums[i]);                 // 选择
                vis[i] = true;                     // 占用
                dfs(nums);                         // 下探下一位置
                path.remove(path.size() - 1);      // 撤销选择
                vis[i] = false;                    // 释放占用
            }
        }
    }
}